src/HOLCF/domain/library.ML
author wenzelm
Thu Jul 14 19:28:24 2005 +0200 (2005-07-14)
changeset 16842 5979c46853d1
parent 16778 2162c0de4673
child 17325 d9d50222808e
permissions -rw-r--r--
tuned;
oheimb@2276
     1
(*  Title:      HOLCF/domain/library.ML
oheimb@2445
     2
    ID:         $Id$
wenzelm@12030
     3
    Author:     David von Oheimb
oheimb@2445
     4
wenzelm@12030
     5
Library for domain section.
regensbu@1274
     6
*)
regensbu@1274
     7
oheimb@2446
     8
oheimb@1637
     9
(* ----- general support ---------------------------------------------------- *)
regensbu@1274
    10
regensbu@1274
    11
fun mapn f n []      = []
regensbu@1274
    12
|   mapn f n (x::xs) = (f n x) :: mapn f (n+1) xs;
regensbu@1274
    13
skalberg@15570
    14
fun foldr'' f (l,f2) = let fun itr []  = raise Fail "foldr''"
oheimb@1637
    15
			     | itr [a] = f2 a
oheimb@1637
    16
			     | itr (a::l) = f(a, itr l)
oheimb@1637
    17
in  itr l  end;
wenzelm@16842
    18
fun foldr' f l = foldr'' f (l,I);
skalberg@15574
    19
fun map_cumulr f start xs = foldr (fn (x,(ys,res))=>case f(x,res) of (y,res2) =>
skalberg@15574
    20
						  (y::ys,res2)) ([],start) xs;
regensbu@1274
    21
regensbu@1274
    22
regensbu@1274
    23
fun first  (x,_,_) = x; fun second (_,x,_) = x; fun third  (_,_,x) = x;
regensbu@1274
    24
fun upd_first  f (x,y,z) = (f x,   y,   z);
regensbu@1274
    25
fun upd_second f (x,y,z) = (  x, f y,   z);
regensbu@1274
    26
fun upd_third  f (x,y,z) = (  x,   y, f z);
regensbu@1274
    27
oheimb@1637
    28
fun atomize thm = let val r_inst = read_instantiate;
oheimb@1637
    29
    fun at  thm = case concl_of thm of
oheimb@1637
    30
      _$(Const("op &",_)$_$_)       => at(thm RS conjunct1)@at(thm RS conjunct2)
oheimb@1637
    31
    | _$(Const("All" ,_)$Abs(s,_,_))=> at(thm RS (r_inst [("x","?"^s)] spec))
oheimb@1637
    32
    | _				    => [thm];
oheimb@1637
    33
in map zero_var_indexes (at thm) end;
regensbu@1274
    34
oheimb@1637
    35
(* ----- specific support for domain ---------------------------------------- *)
regensbu@1274
    36
regensbu@1274
    37
structure Domain_Library = struct
regensbu@1274
    38
oheimb@4122
    39
open HOLCFLogic;
oheimb@4122
    40
regensbu@1274
    41
exception Impossible of string;
regensbu@1274
    42
fun Imposs msg = raise Impossible ("Domain:"^msg);
regensbu@1274
    43
regensbu@1274
    44
(* ----- name handling ----- *)
regensbu@1274
    45
oheimb@1637
    46
val strip_esc = let fun strip ("'" :: c :: cs) = c :: strip cs
oheimb@1637
    47
		    |   strip ["'"] = []
oheimb@1637
    48
		    |   strip (c :: cs) = c :: strip cs
oheimb@1637
    49
		    |   strip [] = [];
wenzelm@4709
    50
in implode o strip o Symbol.explode end;
regensbu@1274
    51
wenzelm@4709
    52
fun extern_name con = case Symbol.explode con of 
oheimb@1637
    53
		   ("o"::"p"::" "::rest) => implode rest
oheimb@1637
    54
		   | _ => con;
regensbu@1274
    55
fun dis_name  con = "is_"^ (extern_name con);
regensbu@1274
    56
fun dis_name_ con = "is_"^ (strip_esc   con);
huffman@16224
    57
fun mat_name  con = "match_"^ (extern_name con);
huffman@16224
    58
fun mat_name_ con = "match_"^ (strip_esc   con);
regensbu@1274
    59
oheimb@1637
    60
(* make distinct names out of the type list, 
oheimb@5292
    61
   forbidding "o","n..","x..","f..","P.." as names *)
oheimb@1637
    62
(* a number string is added if necessary *)
oheimb@4122
    63
fun mk_var_names ids : string list = let
oheimb@5292
    64
    fun nonreserved s = if s mem ["n","x","f","P"] then s^"'" else s;
oheimb@1819
    65
    fun index_vnames(vn::vns,occupied) =
oheimb@1819
    66
          (case assoc(occupied,vn) of
skalberg@15531
    67
             NONE => if vn mem vns
oheimb@1819
    68
                     then (vn^"1") :: index_vnames(vns,(vn,1)  ::occupied)
oheimb@1819
    69
                     else  vn      :: index_vnames(vns,          occupied)
skalberg@15531
    70
           | SOME(i) => (vn^(string_of_int (i+1)))
oheimb@1819
    71
				   :: index_vnames(vns,(vn,i+1)::occupied))
oheimb@1819
    72
      | index_vnames([],occupied) = [];
oheimb@4122
    73
in index_vnames(map nonreserved ids, [("O",0),("o",0)]) end;
regensbu@1274
    74
oheimb@2445
    75
fun rep_Type  (Type  x) = x | rep_Type  _ = Imposs "library:rep_Type";
oheimb@2445
    76
fun rep_TFree (TFree x) = x | rep_TFree _ = Imposs "library:rep_TFree";
oheimb@4122
    77
wenzelm@7652
    78
fun pcpo_type sg t = Sign.of_sort sg (Sign.certify_typ sg t, pcpoS);
oheimb@4008
    79
fun string_of_typ sg = Sign.string_of_typ sg o Sign.certify_typ sg;
oheimb@4008
    80
fun str2typ sg = typ_of o read_ctyp sg;
regensbu@1274
    81
regensbu@1274
    82
(* ----- constructor list handling ----- *)
regensbu@1274
    83
oheimb@1637
    84
type cons = (string *			(* operator name of constr *)
oheimb@1637
    85
	    ((bool*int)*		(*  (lazy,recursive element or ~1) *)
huffman@16394
    86
	      string option*		(*   selector name    *)
oheimb@1637
    87
	      string)			(*   argument name    *)
oheimb@1637
    88
	    list);			(* argument list      *)
oheimb@1637
    89
type eq = (string *		(* name      of abstracted type *)
oheimb@1637
    90
	   typ list) *		(* arguments of abstracted type *)
oheimb@1637
    91
	  cons list;		(* represented type, as a constructor list *)
regensbu@1274
    92
paulson@2238
    93
fun rec_of arg  = snd (first arg);
paulson@2238
    94
fun is_lazy arg = fst (first arg);
regensbu@1274
    95
val sel_of    =       second;
regensbu@1274
    96
val     vname =       third;
regensbu@1274
    97
val upd_vname =   upd_third;
regensbu@1274
    98
fun is_rec         arg = rec_of arg >=0;
regensbu@1274
    99
fun is_nonlazy_rec arg = is_rec arg andalso not (is_lazy arg);
oheimb@1637
   100
fun nonlazy     args   = map vname (filter_out is_lazy    args);
skalberg@15570
   101
fun nonlazy_rec args   = map vname (List.filter is_nonlazy_rec args);
oheimb@1637
   102
huffman@16778
   103
(* ----- qualified names of HOLCF constants ----- *)
huffman@16778
   104
huffman@16778
   105
val lessN      = "Porder.op <<"
huffman@16778
   106
val UU_N       = "Pcpo.UU";
huffman@16778
   107
val admN       = "Adm.adm";
huffman@16778
   108
val Rep_CFunN  = "Cfun.Rep_CFun";
huffman@16778
   109
val Abs_CFunN  = "Cfun.Abs_CFun";
huffman@16778
   110
val ID_N       = "Cfun.ID";
huffman@16778
   111
val cfcompN    = "Cfun.cfcomp";
huffman@16778
   112
val strictifyN = "Cfun.strictify";
huffman@16778
   113
val cpairN     = "Cprod.cpair";
huffman@16778
   114
val cfstN      = "Cprod.cfst";
huffman@16778
   115
val csndN      = "Cprod.csnd";
huffman@16778
   116
val csplitN    = "Cprod.csplit";
huffman@16778
   117
val spairN     = "Sprod.spair";
huffman@16778
   118
val sfstN      = "Sprod.sfst";
huffman@16778
   119
val ssndN      = "Sprod.ssnd";
huffman@16778
   120
val ssplitN    = "Sprod.ssplit";
huffman@16778
   121
val sinlN      = "Ssum.sinl";
huffman@16778
   122
val sinrN      = "Ssum.sinr";
huffman@16778
   123
val sscaseN    = "Ssum.sscase";
huffman@16778
   124
val upN        = "Up.up";
huffman@16778
   125
val fupN       = "Up.fup";
huffman@16778
   126
val ONE_N      = "One.ONE";
huffman@16778
   127
val TT_N       = "Tr.TT";
huffman@16778
   128
val FF_N       = "Tr.FF";
huffman@16778
   129
val iterateN   = "Fix.iterate";
huffman@16778
   130
val fixN       = "Fix.fix";
huffman@16778
   131
val returnN    = "Fixrec.return";
huffman@16778
   132
val failN      = "Fixrec.fail";
huffman@16778
   133
huffman@16778
   134
val pcpoN      = "Pcpo.pcpo"
huffman@16778
   135
val pcpoS      = [pcpoN];
huffman@16778
   136
oheimb@1637
   137
(* ----- support for type and mixfix expressions ----- *)
oheimb@1637
   138
oheimb@1637
   139
infixr 5 -->;
regensbu@1274
   140
regensbu@1274
   141
(* ----- support for term expressions ----- *)
regensbu@1274
   142
berghofe@11531
   143
fun %: s = Free(s,dummyT);
berghofe@11531
   144
fun %# arg = %:(vname arg);
berghofe@11531
   145
fun %%: s = Const(s,dummyT);
regensbu@1274
   146
regensbu@1274
   147
local open HOLogic in
regensbu@1274
   148
val mk_trp = mk_Trueprop;
regensbu@1274
   149
fun mk_conj (S,T) = conj $ S $ T;
regensbu@1274
   150
fun mk_disj (S,T) = disj $ S $ T;
regensbu@1274
   151
fun mk_imp  (S,T) = imp  $ S $ T;
regensbu@1274
   152
fun mk_lam  (x,T) = Abs(x,dummyT,T);
regensbu@1274
   153
fun mk_all  (x,P) = HOLogic.mk_all (x,dummyT,P);
huffman@16778
   154
fun mk_ex   (x,P) = mk_exists (x,dummyT,P);
regensbu@1274
   155
local 
berghofe@11531
   156
		    fun sg [s]     = %:s
berghofe@11531
   157
		    |   sg (s::ss) = %%:"_classes" $ %:s $ sg ss
oheimb@2445
   158
	 	    |   sg _       = Imposs "library:sg";
berghofe@11531
   159
		    fun sf [] = %%:"_emptysort"
berghofe@11531
   160
		    |   sf s  = %%:"_sort" $ sg s
skalberg@15570
   161
		    fun tf (Type (s,args)) = Library.foldl (op $) (%:s,map tf args)
berghofe@11531
   162
		    |   tf (TFree(s,sort)) = %%:"_ofsort" $ %:s $ sf sort
oheimb@2445
   163
		    |   tf _               = Imposs "library:tf";
regensbu@1274
   164
in
berghofe@11531
   165
fun mk_constrain      (typ,T) = %%:"_constrain" $ T $ tf typ;
berghofe@11531
   166
fun mk_constrainall (x,typ,P) = %%:"All" $ (%%:"_constrainAbs" $ mk_lam(x,P) $ tf typ);
regensbu@1274
   167
end;
regensbu@1274
   168
end;
regensbu@1274
   169
berghofe@11531
   170
fun mk_All  (x,P) = %%:"all" $ mk_lam(x,P); (* meta universal quantification *)
regensbu@1274
   171
huffman@16778
   172
infixr 0 ===>;  fun S ===> T = %%:"==>" $ S $ T;
huffman@16778
   173
infixr 0 ==>;   fun S ==> T = mk_trp S ===> mk_trp T;
huffman@16778
   174
infix 0 ==;     fun S ==  T = %%:"==" $ S $ T;
huffman@16778
   175
infix 1 ===;    fun S === T = %%:"op =" $ S $ T;
wenzelm@16842
   176
infix 1 ~=;     fun S ~=  T = HOLogic.mk_not (S === T);
huffman@16778
   177
infix 1 <<;     fun S <<  T = %%:lessN $ S $ T;
wenzelm@16842
   178
infix 1 ~<<;    fun S ~<< T = HOLogic.mk_not (S << T);
regensbu@1274
   179
huffman@16778
   180
infix 9 `  ; fun f`  x = %%:Rep_CFunN $ f $ x;
berghofe@11531
   181
infix 9 `% ; fun f`% s = f` %: s;
berghofe@11531
   182
infix 9 `%%; fun f`%%s = f` %%:s;
skalberg@15570
   183
fun mk_cRep_CFun (F,As) = Library.foldl (op `) (F,As);
berghofe@11531
   184
fun con_app2 con f args = mk_cRep_CFun(%%:con,map f args);
regensbu@1274
   185
fun con_app con = con_app2 con %#;
regensbu@1274
   186
fun if_rec  arg f y   = if is_rec arg then f (rec_of arg) else y;
wenzelm@16842
   187
fun app_rec_arg p arg = if_rec arg (fn n => fn x => (p n)`x) I (%# arg);
oheimb@4754
   188
fun prj _  _  x (   _::[]) _ = x
oheimb@4754
   189
|   prj f1 _  x (_::y::ys) 0 = f1 x y
oheimb@4754
   190
|   prj f1 f2 x (y::   ys) j = prj f1 f2 (f2 x y) ys (j-1);
oheimb@4754
   191
fun fix_tp (tn, args) = (tn, map (K oneT) args); (* instantiate type to
oheimb@4754
   192
						    avoid type varaibles *)
berghofe@11531
   193
fun  proj x      = prj (fn S => K(%%:"fst" $S)) (fn S => K(%%:"snd" $S)) x;
huffman@16778
   194
fun cproj x      = prj (fn S => K(%%:cfstN`S)) (fn S => K(%%:csndN`S)) x;
huffman@15602
   195
fun prj' _  _  x (   _::[]) _ = x
wenzelm@16842
   196
|   prj' f1 _  x (_::   ys) 0 = f1 x (foldr' HOLogic.mk_prodT ys)
huffman@15638
   197
|   prj' f1 f2 x (y::   ys) j = prj' f1 f2 (f2 x y) ys (j-1);
huffman@15602
   198
fun cproj' T eqs = prj'
wenzelm@16842
   199
	(fn S => fn t => Const(cfstN, HOLogic.mk_prodT(dummyT,t)->>dummyT)`S)
wenzelm@16842
   200
	(fn S => fn t => Const(csndN, HOLogic.mk_prodT(t,dummyT)->>dummyT)`S) 
oheimb@4754
   201
		       T (map ((fn tp => tp ->> tp) o Type o fix_tp o fst) eqs);
skalberg@15570
   202
fun lift tfn = Library.foldr (fn (x,t)=> (mk_trp(tfn x) ===> t));
regensbu@1274
   203
huffman@16778
   204
fun /\ v T = %%:Abs_CFunN $ mk_lam(v,T);
regensbu@1274
   205
fun /\# (arg,T) = /\ (vname arg) T;
huffman@16778
   206
infixr 9 oo; fun S oo T = %%:cfcompN`S`T;
huffman@16778
   207
val UU = %%:UU_N;
regensbu@1274
   208
fun strict f = f`UU === UU;
regensbu@1274
   209
fun defined t = t ~= UU;
huffman@16778
   210
fun cpair (S,T) = %%:cpairN`S`T;
huffman@16778
   211
fun mk_ctuple [] = HOLogic.unit (* used in match_defs *)
huffman@16224
   212
|   mk_ctuple (t::[]) = t
huffman@16224
   213
|   mk_ctuple (t::ts) = cpair (t, mk_ctuple ts);
huffman@16224
   214
fun mk_ctupleT [] = HOLogic.unitT   (* used in match_defs *)
huffman@16224
   215
|   mk_ctupleT (T::[]) = T
wenzelm@16842
   216
|   mk_ctupleT (T::Ts) = HOLogic.mk_prodT(T, mk_ctupleT Ts);
regensbu@1274
   217
fun lift_defined f = lift (fn x => defined (f x));
oheimb@4188
   218
fun bound_arg vns v = Bound(length vns -find_index_eq v vns -1);
regensbu@1274
   219
huffman@16778
   220
fun cont_eta_contract (Const("Cfun.Abs_CFun",TT) $ Abs(a,T,body)) = 
regensbu@1274
   221
      (case cont_eta_contract body  of
huffman@16778
   222
        body' as (Const("Cfun.Rep_CFun",Ta) $ f $ Bound 0) => 
oheimb@1637
   223
	  if not (0 mem loose_bnos f) then incr_boundvars ~1 f 
huffman@16778
   224
	  else   Const("Cfun.Abs_CFun",TT) $ Abs(a,T,body')
huffman@16778
   225
      | body' => Const("Cfun.Abs_CFun",TT) $ Abs(a,T,body'))
regensbu@1274
   226
|   cont_eta_contract(f$t) = cont_eta_contract f $ cont_eta_contract t
regensbu@1274
   227
|   cont_eta_contract t    = t;
regensbu@1274
   228
oheimb@1637
   229
fun idx_name dnames s n = s^(if length dnames = 1 then "" else string_of_int n);
oheimb@1834
   230
fun when_funs cons = if length cons = 1 then ["f"] 
oheimb@1834
   231
                     else mapn (fn n => K("f"^(string_of_int n))) 1 cons;
regensbu@1274
   232
fun when_body cons funarg = let
oheimb@1637
   233
	fun one_fun n (_,[]  ) = /\ "dummy" (funarg(1,n))
oheimb@1637
   234
	|   one_fun n (_,args) = let
oheimb@1637
   235
		val l2 = length args;
huffman@16778
   236
		fun idxs m arg = (if is_lazy arg then fn x=> %%:fupN` %%:ID_N`x
wenzelm@16842
   237
					         else I) (Bound(l2-m));
oheimb@1637
   238
		in cont_eta_contract (foldr'' 
huffman@16778
   239
			(fn (a,t) => %%:ssplitN`(/\# (a,t)))
oheimb@1637
   240
			(args,
slotosch@5291
   241
			fn a=> /\#(a,(mk_cRep_CFun(funarg(l2,n),mapn idxs 1 args))))
oheimb@1637
   242
			) end;
oheimb@1637
   243
in (if length cons = 1 andalso length(snd(hd cons)) <= 1
wenzelm@16842
   244
    then fn t => %%:strictifyN`t else I)
huffman@16778
   245
     (foldr' (fn (x,y)=> %%:sscaseN`x`y) (mapn one_fun 1 cons)) end;
regensbu@1274
   246
end; (* struct *)