src/HOLCF/Tools/Domain/domain_library.ML
 author huffman Wed Feb 24 14:20:07 2010 -0800 (2010-02-24) changeset 35443 2e0f9516947e parent 35288 aa7da51ae1ef child 35465 064bb6e9ace0 permissions -rw-r--r--
change domain package's treatment of variable names in theorems to be like datatype package
```     1 (*  Title:      HOLCF/Tools/Domain/domain_library.ML
```
```     2     Author:     David von Oheimb
```
```     3
```
```     4 Library for domain command.
```
```     5 *)
```
```     6
```
```     7
```
```     8 (* ----- general support ---------------------------------------------------- *)
```
```     9
```
```    10 fun mapn f n []      = []
```
```    11   | mapn f n (x::xs) = (f n x) :: mapn f (n+1) xs;
```
```    12
```
```    13 fun foldr'' f (l,f2) =
```
```    14     let fun itr []  = raise Fail "foldr''"
```
```    15           | itr [a] = f2 a
```
```    16           | itr (a::l) = f(a, itr l)
```
```    17     in  itr l  end;
```
```    18
```
```    19 fun map_cumulr f start xs =
```
```    20     List.foldr (fn (x,(ys,res))=>case f(x,res) of (y,res2) =>
```
```    21                                                   (y::ys,res2)) ([],start) xs;
```
```    22
```
```    23 fun first  (x,_,_) = x; fun second (_,x,_) = x; fun third  (_,_,x) = x;
```
```    24 fun upd_first  f (x,y,z) = (f x,   y,   z);
```
```    25 fun upd_second f (x,y,z) = (  x, f y,   z);
```
```    26 fun upd_third  f (x,y,z) = (  x,   y, f z);
```
```    27
```
```    28 fun atomize ctxt thm =
```
```    29     let
```
```    30       val r_inst = read_instantiate ctxt;
```
```    31       fun at thm =
```
```    32           case concl_of thm of
```
```    33             _\$(Const("op &",_)\$_\$_)       => at(thm RS conjunct1)@at(thm RS conjunct2)
```
```    34           | _\$(Const("All" ,_)\$Abs(s,_,_))=> at(thm RS (r_inst [(("x", 0), "?" ^ s)] spec))
```
```    35           | _                             => [thm];
```
```    36     in map zero_var_indexes (at thm) end;
```
```    37
```
```    38 (* infix syntax *)
```
```    39
```
```    40 infixr 5 -->;
```
```    41 infixr 6 ->>;
```
```    42 infixr 0 ===>;
```
```    43 infixr 0 ==>;
```
```    44 infix 0 ==;
```
```    45 infix 1 ===;
```
```    46 infix 1 ~=;
```
```    47 infix 1 <<;
```
```    48 infix 1 ~<<;
```
```    49
```
```    50 infix 9 `  ;
```
```    51 infix 9 `% ;
```
```    52 infix 9 `%%;
```
```    53
```
```    54
```
```    55 (* ----- specific support for domain ---------------------------------------- *)
```
```    56
```
```    57 signature DOMAIN_LIBRARY =
```
```    58 sig
```
```    59   val Imposs : string -> 'a;
```
```    60   val cpo_type : theory -> typ -> bool;
```
```    61   val pcpo_type : theory -> typ -> bool;
```
```    62   val string_of_typ : theory -> typ -> string;
```
```    63
```
```    64   (* Creating HOLCF types *)
```
```    65   val mk_cfunT : typ * typ -> typ;
```
```    66   val ->> : typ * typ -> typ;
```
```    67   val mk_ssumT : typ * typ -> typ;
```
```    68   val mk_sprodT : typ * typ -> typ;
```
```    69   val mk_uT : typ -> typ;
```
```    70   val oneT : typ;
```
```    71   val trT : typ;
```
```    72   val mk_maybeT : typ -> typ;
```
```    73   val mk_ctupleT : typ list -> typ;
```
```    74   val mk_TFree : string -> typ;
```
```    75   val pcpoS : sort;
```
```    76
```
```    77   (* Creating HOLCF terms *)
```
```    78   val %: : string -> term;
```
```    79   val %%: : string -> term;
```
```    80   val ` : term * term -> term;
```
```    81   val `% : term * string -> term;
```
```    82   val /\ : string -> term -> term;
```
```    83   val UU : term;
```
```    84   val TT : term;
```
```    85   val FF : term;
```
```    86   val ID : term;
```
```    87   val oo : term * term -> term;
```
```    88   val mk_up : term -> term;
```
```    89   val mk_sinl : term -> term;
```
```    90   val mk_sinr : term -> term;
```
```    91   val mk_stuple : term list -> term;
```
```    92   val mk_ctuple : term list -> term;
```
```    93   val mk_fix : term -> term;
```
```    94   val mk_iterate : term * term * term -> term;
```
```    95   val mk_fail : term;
```
```    96   val mk_return : term -> term;
```
```    97   val list_ccomb : term * term list -> term;
```
```    98   (*
```
```    99    val con_app : string -> ('a * 'b * string) list -> term;
```
```   100    *)
```
```   101   val con_app2 : string -> ('a -> term) -> 'a list -> term;
```
```   102   val proj : term -> 'a list -> int -> term;
```
```   103   val prj : ('a -> 'b -> 'a) -> ('a -> 'b -> 'a) -> 'a -> 'b list -> int -> 'a;
```
```   104   val mk_ctuple_pat : term list -> term;
```
```   105   val mk_branch : term -> term;
```
```   106
```
```   107   (* Creating propositions *)
```
```   108   val mk_conj : term * term -> term;
```
```   109   val mk_disj : term * term -> term;
```
```   110   val mk_imp : term * term -> term;
```
```   111   val mk_lam : string * term -> term;
```
```   112   val mk_all : string * term -> term;
```
```   113   val mk_ex : string * term -> term;
```
```   114   val mk_constrain : typ * term -> term;
```
```   115   val mk_constrainall : string * typ * term -> term;
```
```   116   val === : term * term -> term;
```
```   117   val << : term * term -> term;
```
```   118   val ~<< : term * term -> term;
```
```   119   val strict : term -> term;
```
```   120   val defined : term -> term;
```
```   121   val mk_adm : term -> term;
```
```   122   val mk_compact : term -> term;
```
```   123   val lift : ('a -> term) -> 'a list * term -> term;
```
```   124   val lift_defined : ('a -> term) -> 'a list * term -> term;
```
```   125
```
```   126   (* Creating meta-propositions *)
```
```   127   val mk_trp : term -> term; (* HOLogic.mk_Trueprop *)
```
```   128   val == : term * term -> term;
```
```   129   val ===> : term * term -> term;
```
```   130   val ==> : term * term -> term;
```
```   131   val mk_All : string * term -> term;
```
```   132
```
```   133       (* Domain specifications *)
```
```   134       eqtype arg;
```
```   135   type cons = string * mixfix * arg list;
```
```   136   type eq = (string * typ list) * cons list;
```
```   137   val mk_arg : (bool * Datatype.dtyp) * string option * string -> arg;
```
```   138   val is_lazy : arg -> bool;
```
```   139   val rec_of : arg -> int;
```
```   140   val dtyp_of : arg -> Datatype.dtyp;
```
```   141   val sel_of : arg -> string option;
```
```   142   val vname : arg -> string;
```
```   143   val upd_vname : (string -> string) -> arg -> arg;
```
```   144   val is_rec : arg -> bool;
```
```   145   val is_nonlazy_rec : arg -> bool;
```
```   146   val nonlazy : arg list -> string list;
```
```   147   val nonlazy_rec : arg list -> string list;
```
```   148   val %# : arg -> term;
```
```   149   val /\# : arg * term -> term;
```
```   150   val when_body : cons list -> (int * int -> term) -> term;
```
```   151   val when_funs : 'a list -> string list;
```
```   152   val bound_arg : ''a list -> ''a -> term; (* ''a = arg or string *)
```
```   153   val idx_name : 'a list -> string -> int -> string;
```
```   154   val app_rec_arg : (int -> term) -> arg -> term;
```
```   155   val con_app : string -> arg list -> term;
```
```   156   val dtyp_of_eq : eq -> Datatype.dtyp;
```
```   157
```
```   158
```
```   159   (* Name mangling *)
```
```   160   val strip_esc : string -> string;
```
```   161   val extern_name : string -> string;
```
```   162   val dis_name : string -> string;
```
```   163   val mat_name : string -> string;
```
```   164   val pat_name : string -> string;
```
```   165 end;
```
```   166
```
```   167 structure Domain_Library :> DOMAIN_LIBRARY =
```
```   168 struct
```
```   169
```
```   170 exception Impossible of string;
```
```   171 fun Imposs msg = raise Impossible ("Domain:"^msg);
```
```   172
```
```   173 (* ----- name handling ----- *)
```
```   174
```
```   175 val strip_esc =
```
```   176     let fun strip ("'" :: c :: cs) = c :: strip cs
```
```   177           | strip ["'"] = []
```
```   178           | strip (c :: cs) = c :: strip cs
```
```   179           | strip [] = [];
```
```   180     in implode o strip o Symbol.explode end;
```
```   181
```
```   182 fun extern_name con =
```
```   183     case Symbol.explode con of
```
```   184       ("o"::"p"::" "::rest) => implode rest
```
```   185     | _ => con;
```
```   186 fun dis_name  con = "is_"^ (extern_name con);
```
```   187 fun dis_name_ con = "is_"^ (strip_esc   con);
```
```   188 fun mat_name  con = "match_"^ (extern_name con);
```
```   189 fun mat_name_ con = "match_"^ (strip_esc   con);
```
```   190 fun pat_name  con = (extern_name con) ^ "_pat";
```
```   191 fun pat_name_ con = (strip_esc   con) ^ "_pat";
```
```   192
```
```   193 fun cpo_type sg t = Sign.of_sort sg (Sign.certify_typ sg t, @{sort cpo});
```
```   194 fun pcpo_type sg t = Sign.of_sort sg (Sign.certify_typ sg t, @{sort pcpo});
```
```   195 fun string_of_typ sg = Syntax.string_of_typ_global sg o Sign.certify_typ sg;
```
```   196
```
```   197 (* ----- constructor list handling ----- *)
```
```   198
```
```   199 type arg =
```
```   200      (bool * Datatype.dtyp) *   (*  (lazy, recursive element) *)
```
```   201      string option *               (*   selector name    *)
```
```   202      string;                       (*   argument name    *)
```
```   203
```
```   204 type cons =
```
```   205      string *         (* operator name of constr *)
```
```   206      mixfix *         (* mixfix syntax of constructor *)
```
```   207      arg list;        (* argument list      *)
```
```   208
```
```   209 type eq =
```
```   210      (string *        (* name      of abstracted type *)
```
```   211       typ list) *     (* arguments of abstracted type *)
```
```   212      cons list;       (* represented type, as a constructor list *)
```
```   213
```
```   214 val mk_arg = I;
```
```   215
```
```   216 fun rec_of ((_,dtyp),_,_) =
```
```   217     case dtyp of Datatype_Aux.DtRec i => i | _ => ~1;
```
```   218 (* FIXME: what about indirect recursion? *)
```
```   219
```
```   220 fun is_lazy arg = fst (first arg);
```
```   221 fun dtyp_of arg = snd (first arg);
```
```   222 val sel_of    =       second;
```
```   223 val     vname =       third;
```
```   224 val upd_vname =   upd_third;
```
```   225 fun is_rec         arg = rec_of arg >=0;
```
```   226 fun is_nonlazy_rec arg = is_rec arg andalso not (is_lazy arg);
```
```   227 fun nonlazy     args   = map vname (filter_out is_lazy args);
```
```   228 fun nonlazy_rec args   = map vname (filter is_nonlazy_rec args);
```
```   229
```
```   230
```
```   231 (* ----- combinators for making dtyps ----- *)
```
```   232
```
```   233 fun mk_uD T = Datatype_Aux.DtType(@{type_name "u"}, [T]);
```
```   234 fun mk_sprodD (T, U) = Datatype_Aux.DtType(@{type_name "**"}, [T, U]);
```
```   235 fun mk_ssumD (T, U) = Datatype_Aux.DtType(@{type_name "++"}, [T, U]);
```
```   236 fun mk_liftD T = Datatype_Aux.DtType(@{type_name "lift"}, [T]);
```
```   237 val unitD = Datatype_Aux.DtType(@{type_name "unit"}, []);
```
```   238 val boolD = Datatype_Aux.DtType(@{type_name "bool"}, []);
```
```   239 val oneD = mk_liftD unitD;
```
```   240 val trD = mk_liftD boolD;
```
```   241 fun big_sprodD ds = case ds of [] => oneD | _ => foldr1 mk_sprodD ds;
```
```   242 fun big_ssumD ds = case ds of [] => unitD | _ => foldr1 mk_ssumD ds;
```
```   243
```
```   244 fun dtyp_of_arg ((lazy, D), _, _) = if lazy then mk_uD D else D;
```
```   245 fun dtyp_of_cons (_, _, args) = big_sprodD (map dtyp_of_arg args);
```
```   246 fun dtyp_of_eq (_, cons) = big_ssumD (map dtyp_of_cons cons);
```
```   247
```
```   248
```
```   249 (* ----- support for type and mixfix expressions ----- *)
```
```   250
```
```   251 fun mk_uT T = Type(@{type_name "u"}, [T]);
```
```   252 fun mk_cfunT (T, U) = Type(@{type_name "->"}, [T, U]);
```
```   253 fun mk_sprodT (T, U) = Type(@{type_name "**"}, [T, U]);
```
```   254 fun mk_ssumT (T, U) = Type(@{type_name "++"}, [T, U]);
```
```   255 val oneT = @{typ one};
```
```   256 val trT = @{typ tr};
```
```   257
```
```   258 val op ->> = mk_cfunT;
```
```   259
```
```   260 fun mk_TFree s = TFree ("'" ^ s, @{sort pcpo});
```
```   261
```
```   262 (* ----- support for term expressions ----- *)
```
```   263
```
```   264 fun %: s = Free(s,dummyT);
```
```   265 fun %# arg = %:(vname arg);
```
```   266 fun %%: s = Const(s,dummyT);
```
```   267
```
```   268 local open HOLogic in
```
```   269 val mk_trp = mk_Trueprop;
```
```   270 fun mk_conj (S,T) = conj \$ S \$ T;
```
```   271 fun mk_disj (S,T) = disj \$ S \$ T;
```
```   272 fun mk_imp  (S,T) = imp  \$ S \$ T;
```
```   273 fun mk_lam  (x,T) = Abs(x,dummyT,T);
```
```   274 fun mk_all  (x,P) = HOLogic.mk_all (x,dummyT,P);
```
```   275 fun mk_ex   (x,P) = mk_exists (x,dummyT,P);
```
```   276 val mk_constrain = uncurry TypeInfer.constrain;
```
```   277 fun mk_constrainall (x,typ,P) = %%:"All" \$ (TypeInfer.constrain (typ --> boolT) (mk_lam(x,P)));
```
```   278 end
```
```   279
```
```   280 fun mk_All  (x,P) = %%:"all" \$ mk_lam(x,P); (* meta universal quantification *)
```
```   281
```
```   282 infixr 0 ===>;  fun S ===> T = %%:"==>" \$ S \$ T;
```
```   283 infixr 0 ==>;   fun S ==> T = mk_trp S ===> mk_trp T;
```
```   284 infix 0 ==;     fun S ==  T = %%:"==" \$ S \$ T;
```
```   285 infix 1 ===;    fun S === T = %%:"op =" \$ S \$ T;
```
```   286 infix 1 ~=;     fun S ~=  T = HOLogic.mk_not (S === T);
```
```   287 infix 1 <<;     fun S <<  T = %%: @{const_name Porder.below} \$ S \$ T;
```
```   288 infix 1 ~<<;    fun S ~<< T = HOLogic.mk_not (S << T);
```
```   289
```
```   290 infix 9 `  ; fun f ` x = %%: @{const_name Rep_CFun} \$ f \$ x;
```
```   291 infix 9 `% ; fun f`% s = f` %: s;
```
```   292 infix 9 `%%; fun f`%%s = f` %%:s;
```
```   293
```
```   294 fun mk_adm t = %%: @{const_name adm} \$ t;
```
```   295 fun mk_compact t = %%: @{const_name compact} \$ t;
```
```   296 val ID = %%: @{const_name ID};
```
```   297 fun mk_strictify t = %%: @{const_name strictify}`t;
```
```   298 (*val csplitN    = "Cprod.csplit";*)
```
```   299 (*val sfstN      = "Sprod.sfst";*)
```
```   300 (*val ssndN      = "Sprod.ssnd";*)
```
```   301 fun mk_ssplit t = %%: @{const_name ssplit}`t;
```
```   302 fun mk_sinl t = %%: @{const_name sinl}`t;
```
```   303 fun mk_sinr t = %%: @{const_name sinr}`t;
```
```   304 fun mk_sscase (x, y) = %%: @{const_name sscase}`x`y;
```
```   305 fun mk_up t = %%: @{const_name up}`t;
```
```   306 fun mk_fup (t,u) = %%: @{const_name fup} ` t ` u;
```
```   307 val ONE = @{term ONE};
```
```   308 val TT = @{term TT};
```
```   309 val FF = @{term FF};
```
```   310 fun mk_iterate (n,f,z) = %%: @{const_name iterate} \$ n ` f ` z;
```
```   311 fun mk_fix t = %%: @{const_name fix}`t;
```
```   312 fun mk_return t = %%: @{const_name Fixrec.return}`t;
```
```   313 val mk_fail = %%: @{const_name Fixrec.fail};
```
```   314
```
```   315 fun mk_branch t = %%: @{const_name Fixrec.branch} \$ t;
```
```   316
```
```   317 val pcpoS = @{sort pcpo};
```
```   318
```
```   319 val list_ccomb = Library.foldl (op `); (* continuous version of list_comb *)
```
```   320 fun con_app2 con f args = list_ccomb(%%:con,map f args);
```
```   321 fun con_app con = con_app2 con %#;
```
```   322 fun if_rec  arg f y   = if is_rec arg then f (rec_of arg) else y;
```
```   323 fun app_rec_arg p arg = if_rec arg (fn n => fn x => (p n)`x) I (%# arg);
```
```   324 fun prj _  _  x (   _::[]) _ = x
```
```   325   | prj f1 _  x (_::y::ys) 0 = f1 x y
```
```   326   | prj f1 f2 x (y::   ys) j = prj f1 f2 (f2 x y) ys (j-1);
```
```   327 fun  proj x      = prj (fn S => K(%%:"fst" \$S)) (fn S => K(%%:"snd" \$S)) x;
```
```   328 fun lift tfn = Library.foldr (fn (x,t)=> (mk_trp(tfn x) ===> t));
```
```   329
```
```   330 fun /\ v T = %%: @{const_name Abs_CFun} \$ mk_lam(v,T);
```
```   331 fun /\# (arg,T) = /\ (vname arg) T;
```
```   332 infixr 9 oo; fun S oo T = %%: @{const_name cfcomp}`S`T;
```
```   333 val UU = %%: @{const_name UU};
```
```   334 fun strict f = f`UU === UU;
```
```   335 fun defined t = t ~= UU;
```
```   336 fun cpair (t,u) = %%: @{const_name Pair} \$ t \$ u;
```
```   337 fun spair (t,u) = %%: @{const_name spair}`t`u;
```
```   338 fun mk_ctuple [] = HOLogic.unit (* used in match_defs *)
```
```   339   | mk_ctuple ts = foldr1 cpair ts;
```
```   340 fun mk_stuple [] = ONE
```
```   341   | mk_stuple ts = foldr1 spair ts;
```
```   342 fun mk_ctupleT [] = HOLogic.unitT   (* used in match_defs *)
```
```   343   | mk_ctupleT Ts = foldr1 HOLogic.mk_prodT Ts;
```
```   344 fun mk_maybeT T = Type ("Fixrec.maybe",[T]);
```
```   345 fun cpair_pat (p1,p2) = %%: @{const_name cpair_pat} \$ p1 \$ p2;
```
```   346 val mk_ctuple_pat = foldr1 cpair_pat;
```
```   347 fun lift_defined f = lift (fn x => defined (f x));
```
```   348 fun bound_arg vns v = Bound (length vns - find_index (fn v' => v' = v) vns - 1);
```
```   349
```
```   350 fun cont_eta_contract (Const("Cfun.Abs_CFun",TT) \$ Abs(a,T,body)) =
```
```   351     (case cont_eta_contract body  of
```
```   352        body' as (Const("Cfun.Rep_CFun",Ta) \$ f \$ Bound 0) =>
```
```   353        if not (0 mem loose_bnos f) then incr_boundvars ~1 f
```
```   354        else   Const("Cfun.Abs_CFun",TT) \$ Abs(a,T,body')
```
```   355      | body' => Const("Cfun.Abs_CFun",TT) \$ Abs(a,T,body'))
```
```   356   | cont_eta_contract(f\$t) = cont_eta_contract f \$ cont_eta_contract t
```
```   357   | cont_eta_contract t    = t;
```
```   358
```
```   359 fun idx_name dnames s n = s^(if length dnames = 1 then "" else string_of_int n);
```
```   360 fun when_funs cons = if length cons = 1 then ["f"]
```
```   361                      else mapn (fn n => K("f"^(string_of_int n))) 1 cons;
```
```   362 fun when_body cons funarg =
```
```   363     let
```
```   364       fun one_fun n (_,_,[]  ) = /\ "dummy" (funarg(1,n))
```
```   365         | one_fun n (_,_,args) = let
```
```   366             val l2 = length args;
```
```   367             fun idxs m arg = (if is_lazy arg then (fn t => mk_fup (ID, t))
```
```   368                               else I) (Bound(l2-m));
```
```   369           in cont_eta_contract
```
```   370                (foldr''
```
```   371                   (fn (a,t) => mk_ssplit (/\# (a,t)))
```
```   372                   (args,
```
```   373                 fn a=> /\#(a,(list_ccomb(funarg(l2,n),mapn idxs 1 args))))
```
```   374                ) end;
```
```   375     in (if length cons = 1 andalso length(third(hd cons)) <= 1
```
```   376         then mk_strictify else I)
```
```   377          (foldr1 mk_sscase (mapn one_fun 1 cons)) end;
```
```   378
```
```   379 end; (* struct *)
```